1. Field of the Invention
The present invention relates to an image processing device utilized by a computer and in particular to an image processing device and method thereof that can efficiently determine a shadow region of an object.
2. Description of the Related Art
Shadow polygon methods have been proposed which allow a shadow of an object to be drawn utilizing hidden-surface cancellation processing hardware that uses the Z-value in image processing. For example, this method is proposed in unexamined patent publication, KOKAI HEI 2-73479. This type of shadow polygon method utilizes a virtual object for the purpose of shadow-casting. This is called shadow volume. A shadow volume is a shadow space produced by a light source and an object that shields the light. The inner side of this shadow volume is the region that becomes the shadow for an object and the outer side is the region irradiated by the light from the light source.
A shadow volume is a semi-infinite polyhedron and the plurality of sidewalls comprising this polyhedron are semi-infinite polygons called shadow polygons. Therefore, a shadow volume is comprised by a plurality of shadow polygons. The shadow polygons are handled in like manner to ordinary polygons thereby allowing shadowing.
FIG. 1 shows a shadow process utilizing shadow volumes and shadow polygons which comprise the shadow volumes. In this example, shadow volumes SV1, SV2 and SV3 are formed by means of blocking light from the light source by opaque polygons P1, P2 and P3. Because the light source is on the left side in the figure, shadow volumes SV1, SV2 and SV3 are generated on the right sides of opaque polygons P1, P2 and P3, respectively. Further, cross sections of the shadow volumes are shown in the figure. Therefore, shadow volume SV1 is formed by shadow polygons SP11 and SP12, shadow volume SV2 is formed by shadow polygons SP21 and SP22, and shadow volume SV3 is formed by shadow polygons SP31 and SP32.
At the present, the position of the view point is temporarily at view point 1 of a position outside the shadow volumes. In order to detect either the region of a shadow inside a shadow volume or the region irradiated by outside light, shadow polygons passing through in the direction of the Z-axis (direction of arrow) from view point 1 to a normal polygon are counted and then that count value is detected as either an even number or an odd number. As shown in FIG. 1, when view point 1 is positioned at the outer side of a shadow volumes, it is understood that if the count value is an even number, the region is outside a shadow volume and if the count value is an odd number, the region is inside a shadow volume.
Therefore, in order to judge whether the surface of a certain polygon is a region of a shadow, the number of shadow polygons existing in front of the position of that certain polygon, namely, between the position of that polygon and the position of the view point can be counted and then if that count value is an even number, the region is inside a shadow and if the count value is an odd number, the region is outside a shadow.
For example, if ordinary polygon OP exists intersecting shadow volume SV3 as shown in FIG. 1, two shadow polygons SP31 and SP32 exist between the a-b region of ordinary polygon OP and the view point 1. Because of this, the region a-b is judged to be a region outside shadow volume SV3. Furthermore, one shadow polygon SP32 exists between the b-c region of ordinary polygon OP and the view point 1. Because of this, the b-c region is judged to be a region inside shadow volume SV3. Even further, because no shadow polygons exist between the c-d region and the view point 1, the c-d region is judged to be a region outside shadow volume SV3.
As described above, shadow processing that utilizes shadow volumes and shadow polygons utilize a method similar to a hidden-surface cancellation method that uses Z-values, allowing the number of shadow polygons which exist between a certain polygon and a view point to be counted.
However, when the view point is positioned inside a shadow volume as seen by view point 2 in FIG. 1, if the number of shadow polygons between the view point 2 and the ordinary polygons is an odd number, the region is outside a shadow volume and if it is an even number, the region is inside a shadow volume. In other words, when the view point is positioned inside a shadow volume, the relationship between a region outside a shadow and a region inside a shadow for an odd number and an even number of polygons up to the view point is reversed compared to when the view point is positioned outside a shadow volume.
Therefore, in a conventional shadow processing method, it is necessary to judge whether the position of the view point is outside the shadow volume or inside the shadow volume. This judgment is, for example, necessary to carry out complicated calculations such as finding an equation of the surfaces of a shadow polygon. Further, depending on the results of the judgment, it must be necessary to change the relationship between the even/odd number of shadow polygons positioned between an ordinary polygon and an view point and whether the region is inside or outside a shadow.
Thereupon, the object of the present invention is to solve the above-mentioned conventional problems and provide an image processing device and method thereof that can carry out shadow processing to produce shadows with even more efficiency.
A further object of the present invention is to provide a recording medium that records a program that can carry out shadow processing to produce shadows with even more efficiency.
In order to achieve the above-mentioned objectives, provided is an image processing device comprising:
a pixel data generation step for generating position data and depth data in a display screen for pixels of first ordinary polygons, and generating position data and depth data in a display screen for pixels of shadow polygons which specify a shadow space produced by second ordinary polygon blocking light from a light source;
a step for storing the depth data for pixels the first ordinary polygons with the shortest depth at each pixel position;
a shadow determination step for detecting whether said shadow polygons exist between the stored depth position of pixels and an infinite position for each pixel position, detecting either an odd or even number of shadow polygons existing between the two positions, and determining that a shadow exists at said pixel when the number of shadow polygons is an odd number and;
a rendering step for carrying out a shadowing process for pixels judged to have shadow by said shadow determination step.
According to the image processing method above, when the number of shadow polygons existing between a depth position of pixels of ordinary polygons subject to shadowing and an infinite position is counted and that number is an odd number, those pixels are unconditionally judged to be positioned inside a region of shadow volume. Therefore, regions to undergo shadowing can be efficiently detected by judging whether the number is an odd number or an even number at all pixel positions.
Furthermore, in order to achieve the above-mentioned objectives, provided is an image processing device comprising:
a pixel data generation step for generating position data and depth data in a display screen for pixels of first ordinary polygons, and generating position data and depth data in a display screen for pixels of shadow polygons which specify a shadow space produced by second ordinary polygon blocking light from a light source;
a step for storing the depth data for pixels of the first ordinary polygons with the shortest depth at each pixel position;
a shadow determination step for detecting whether said shadow polygons exist between the stored depth position of pixels and an infinite position for each pixel position, and determining whether a shadow exists at said pixel in accordance with the number of shadow polygons existing between the two positions and;
a rendering step for carrying out a shadowing process for pixels judged to have shadow by said shadow determination step.
As described above, because it is possible to judge whether a shadow exists at a pixel in accordance with the number of shadow polygons existing between the stored depth position of pixels of first ordinary polygons and an infinite position, a shadowing process can be executed using a simple algorithm. In particular, when an infinite position is positioned inside a shadow volume, shadowing is carried out when the number of polygons detected above is an even number. Further, when an infinite position is positioned outside a shadow volume, shadowing is carried out when the number of polygons detected above is an odd number.
The present invention also includes and image processing device that executes the above-mentioned image processing method and a computer readable recording medium that records an image processing program to have a computer execute the image processing method.